// 题目要求：
// 给一个 n，表示有 n 种字符组成一个字符串，再给 n 个整数，表示每种字符出现的次数
// 要求使用哈夫曼编码处理，求处理完的哈夫曼编码和最短长度

// 解题思路：
// 根据输入的 n 个整数，创建一棵二叉树，方法如下：
// 根据输入的 n 个整数，创建 n 个二叉树的节点，存放到小根堆中
// 每次取出两个最小的节点，以这两个节点的值的和，创建一个根节点，这两个节点分别为左子树和右子树
// 再把这棵树的根节点放到堆中
// 重复上述步骤，直到队列中只剩下一个节点，这棵树就创建完成了

// 遍历二叉树，收集哈夫曼编码：
// 如果左子树存在，就收集一个 0，到叶子节点后，将收集的哈夫曼编码添加到结果表中
// 如果右子树存在，就收集一个 1，到叶子节点后，将收集的哈夫曼编码添加到结果表中
// 每到一个节点，就收集节点的值，最后减去根节点的值，就是压缩后的字符串的最小长度

import java.util.*;

public class HuffmanCoding {
    public static Scanner in = new Scanner(System.in);
    public static int n = 0;
    public static List<List<Integer>> result = new ArrayList<>();
    public static List<Integer> path = new ArrayList<>();
    public static long pathLength = 0;

    public static void main(String[] args) {
        n = in.nextInt();

        TreeNode root = createTree();
        TreeNode cur = root;

        dfs(cur);
        for(List<Integer> list : result){
            for(int i = 0; i < list.size(); i++){
                System.out.print(list.get(i) + " ");
            }
            System.out.println();
        }

        System.out.println(pathLength - root.val);
    }

    public static void dfs(TreeNode cur){
        if(cur == null) return;
        //System.out.print(cur.val + " ");
        pathLength += cur.val;
        if(cur.left == null && cur.right == null){
            result.add(new ArrayList<>(path));
            return;
        }
        if(cur.left != null) {
            path.add(0);
            dfs(cur.left);
            path.remove(path.size() - 1);
        }
        if(cur.right != null) {
            path.add(1);
            dfs(cur.right);
            path.remove(path.size() - 1);
        }

    }

    public static TreeNode createTree() {
        PriorityQueue<TreeNode> heap = new PriorityQueue<>((a, b) -> {
            if(a.val > b.val) return 1;
            else return -1;
        });

        for (int i = 0; i < n; i++) {
            long t = in.nextLong();
            TreeNode node = new TreeNode(t);
            heap.offer(node);
        }

        while (heap.size() != 1) {
            TreeNode left = heap.poll();
            TreeNode right = heap.poll();
            TreeNode root = new TreeNode(left.val + right.val);

            root.left = left;
            root.right = right;

            if(heap.isEmpty()){
                return root;
            }

            heap.offer(root);
        }

        return null;
    }

    static class TreeNode {
        public long val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(long val) {
            this.val = val;
        }
    }
}
